1. Field of the Invention
The invention relates to the allocation of bandwidth in an ATM (Asynchronous Transfer Mode) network. More particularly, the invention relates to methods and apparatus for the fair allocation of bandwidth among minimum cell rate (MCR) and best effort service connections.
2. State of the Art
Perhaps the most awaited, and now fastest growing technology in the field of telecommunications is known as Asynchronous Transfer Mode (ATM) technology. ATM was designed to be a carrier of integrated traffic, e.g. voice, data, and video. ATM utilizes fixed length packets (called “cells”) of 53 octets (5 octets header and 48 octets payload). Current ATM service is offered in different categories according to a user's needs. These categories include, in order of priority: constant bit rate (CBR), variable bit rate-real time (VBR or VBR-rt), variable bit rate-non-real time (VBR-nrt), guaranteed frame rate (GFR), available bit rate (ABR), unspecified bit rate plus (UBR+), and unspecified bit rate (UBR). CBR and VBR-rt are “real-time” categories suitable for streaming video and voice connections. These categories are given the highest priority in the ATM network. The other five categories are considered “non-real-time”. For GFR, ABR, and UBR+, users pay for a minimum cell rate (or guaranteed frame rate) which is an average rate taken over time during which there may be bursty periods and periods of latency. For convenience, these four categories are referred to as MCR (minimum cell rate) services. For UBR, no minimum bandwidth is guaranteed. UBR connections are serviced last if there is any available bandwidth after servicing all of the higher categories of service. UBR, is referred to as “best effort” service.
One of the most difficult aspects of implementing traffic control in an ATM network is the fair allocation of available bandwidth that is not required by high priority connections or to meet MCR requirements of low priority traffic. Presently, there are several different ways to apportion extra bandwidth.
The simplest way is to put all the GFR, ABR, and UBR+ traffic in a single queue and allocate priority to the queue higher than UBR traffic but lower than real time traffic. This method does not guarantee the MCR traffic the “contracted-for” minimum bandwidth and does not assure that best effort connections are allocated bandwidth fairly.
Another method for allocating bandwidth is to provide a separate queue for each connection (per-VC queuing) and service the queues in a round robin-fashion. This guarantees fairness but does not, by itself, guarantee the MCR traffic the “contracted-for” minimum bandwidth.
Still another method is to provide per-VC queuing, shape the individual connections, and service the queues using a best effort round robin mechanism. This method provides the individual bandwidth guarantees to MCR connections and provides a fair allocation of remaining bandwidth to the best effort connections. However, the shaping mechanism is typically shared among all service categories, including real-time categories.
“Overbooking” is the allocation of more bandwidth than is actually available to MCR and best effort connections in order to take advantage of statistical multiplexing. Overbooking would adversely affect the real-time traffic in this single level type of scheduler and thus must be avoided in this type of implementation.